public class Solution {
    //不同路径
    /*空间复杂度m*n
    * 时间复杂度m*n
    * */
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[1][0] = 1;
        for (int i = 0; i <= m ; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
    //不同路径2
    /*
    * 空间复杂度m*n
    * 时间复杂度m*n
    * */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        //初始化
        dp[0][1] = 1;
        //填表
        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                if(obstacleGrid[i-1][j-1] != 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[obstacleGrid.length][obstacleGrid[0].length];
    }
    //珠宝最大价值
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
            }
        }
        return dp[m][n];
    }
    //最小下降问题
    //矩形
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n+1][n+2];
        for(int i = 1; i<= n;i++) {
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;
        }
        for(int i = 1; i<=n;i++){
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];
            }
        }
        int ret = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            ret = Math.min(ret,dp[n][i]);
        }
        return ret;
    }
}
